package algorthm.systemTraning.quickSort;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Arrays;
import java.util.Random;

/**
 * @className: NumberComparator
 * @Description:
 * @Author: wangyifei
 * @Date: 2022/9/28 10:17
 */
public class NumberComparator {
    private static Logger logger = LoggerFactory.getLogger(NumberComparator.class);
    public static int[] netherlandsFlag(int[] array , int start , int end){
        int[] lt = new int[end - start + 1];
        int[] eq = new int[end - start + 1];
        int[] gt = new int[end - start + 1];
        int ltIdx = 0 ;
        int gtIdx = 0 ;
        int eqIdx = 0 ;
        for(int i = start ; i < end ; i++){
            if(array[i] < array[end]){
                lt[ltIdx++] = array[i] ;
            }else if(array[i] > array[end]){
                gt[gtIdx++] = array[i];
            }else{
                eq[eqIdx++] = array[i];
            }
        }
        for(int j = 0 ; j < ltIdx ; j++){
            array[start + j] = lt[j];
        }
        for(int j = 0 ; j < eqIdx ; j++){
            array[start + ltIdx + j] = eq[j];
        }
        array[start + ltIdx + eqIdx] = array[end];
        for(int j = 0 ; j < gtIdx ; j++){
            array[start + 1 + ltIdx + eqIdx + j] = gt[j];
        }
        return new int[]{start + ltIdx , start + ltIdx + eqIdx};
    }
    public static int[] randomArray(int range , int size){
        Random r = new Random();
        int[] array = new int[r.nextInt(size) + 1];
        for(int i = 0 ; i < array.length ; i++){
            array[i] = r.nextInt(range);
        }
        return array ;
    }
    public static int[] copyOf(int[] array){
        int[] rs = new int[array.length];
        for(int i = 0 ; i < array.length ; i++){
            rs[i] = array[i];
        }
        return rs ;
    }
    public static void compare(int range , int size , int times){
        int[] array = null ;
        int[] array1 = null ;
        int[] arrayBackup = null ;
        int[] ans1 = null ;
        int[] ans2 = null ;
        for(int i = 0 ; i < times ; i++){
            array = randomArray(range , size);
            array1 = copyOf(array);
            arrayBackup = copyOf(array);
            ans1 = netherlandsFlag(array , 0 , array.length - 1);
            ans2 = QuickSort.netherlandsFlag(array1 , 0 , array1.length - 1);
            if(ans1 != null && ans2 != null && (ans1[0] != ans2[0] || ans1[1] != ans2[1])){
                System.out.println("1:not equal,arrayis:" + Arrays.toString(arrayBackup));
                System.out.println("ans1:" + ans1[0] + "," + ans1[1] + " ans2:" + ans2[0] + "," + ans2[1]);
            }
            if(ans1 == null || ans2 == null){
                System.out.println("2:not equal , array is:" + Arrays.toString(arrayBackup));
            }else{
                if(ans1.length != ans2.length){
                    System.out.println("3:not equal , array is:" + Arrays.toString(arrayBackup));
                }
            }
        }
    }
    public static void compareQuickSort(int range , int size , int times){
        Random r = new Random();
        int s = r.nextInt(size) + 1;
        int[] array = null ;
        int[] array1 = null ;
        int[] arrayBack = null ;
        for(int i = 0 ; i < times ; i++){
            array = randomArray(range , size);
            array1 = copyOf(array);
            arrayBack = copyOf(array);
            Arrays.sort(array);
//            QuickSort.sort(array1);
//            QuickSort.sortWithStack(array1);
            QuickSort.sortWithQueue(array1);
            if(!Arrays.equals(array , array1)){
                System.out.println("not equal , array is:" + Arrays.toString(arrayBack));
            }
        }
    }
    public static void main(String[] agrs){
//        compare(100 , 32 , 98776);
        compareQuickSort(100 , 43 , 988721);
    }
}
